'''
https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-interview-150
'''


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    # 1. 不含自己：左右边最大
    # 2. 含自己可以给上级用：[父节点路径值]+自己+[向左或向右]
    # 3. 含自己不能给上级用：自己+向左+向右
    # 后续遍历处理：
    #       需要下级提供，包含子节点的最大值
    def maxPathSum(self, root: TreeNode) -> int:
        def f(root):
            if not root: return float('-inf'), float('-inf')
            lmax, lmax_with_left = f(root.left)
            rmax, rmax_with_right = f(root.right)
            maxsum_no_me = max(lmax, rmax)
            maxsum_with_me = max(root.val, root.val + lmax_with_left, root.val + rmax_with_right)
            maxsum = max(maxsum_no_me, maxsum_with_me, root.val + lmax_with_left + rmax_with_right)
            return maxsum, maxsum_with_me
        return f(root)[0]
